#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sxlb.h"

//1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList(){
    double_node_t* p=(double_node_t*)malloc(sizeof(double_node_t));
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return NULL;
    }
    link_node_t* head=(link_node_t*)malloc(sizeof(link_node_t));
    if(p == NULL){
        printf("头内存分配错误!\n");
        free(p);
        p=NULL;
        return NULL;
    }
    memset(head,0,sizeof(link_node_t));
    p->head=p->tail=head;
    p->len=0;
    return p;
}

//2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
    link_node_t*new=(link_node_t*)malloc(sizeof(link_node_t));
    if(new == NULL){
        printf("节点内存分配错误!\n");
        return -1;
    }
    
    if(0 <= post && post < p->len){
        link_node_t* temp=p->head->next;//用temp指代第一个节点，
        for(int i =0;i<post;i++){   //遍历使temp指代插入节点，
            temp=temp->next;
        }
        new->data=data;
        (temp->prior)->next=new;
        new->prior=temp->prior;
        temp->prior=new;
        new->next=temp;
        p->len++;
        return 0;
    }
    else if(post == p->len){
        new->data=data;
        link_node_t* temp=p->tail;//用temp指代最后一个节点，
        temp->next=new;
        p->tail=new;
        new->prior=temp;
        new->next=NULL;
        p->len++;
        return 0;
    }
    else{
        printf("插入位置不合法!\n");
        free(new);
        new=NULL;
        return -1;
    }


}

//3.遍历双向链表
void showDoubleLinkList(const double_list_t p){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return ;
    }
    if(isEmptyDoubleLinkList(p) == 0){
        printf("链表为空");
        return;
    }
    link_node_t* temp=p->head->next;
    int i=0;
    while(temp != NULL){
        printf("第%d 位元素: %d\n",i,temp->data);
        temp=temp->next;
        i++;
    }
    temp=p->tail;
    for(int i = 0;i < p->len;i++){
        printf("第%d 位元素: %d\n",p->len-i-1,temp->data);
        temp=temp->prior;
    }
}

//4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
    if(p->len <= post || post < 0){
        printf("位置不合法!\n");
        return -1;
    }
    if(post == p->len-1){
       link_node_t* temp=p->tail;//用temp指代最后一个节点，
        temp->prior->next=NULL;
        p->tail=temp->prior;
        free(temp);
        p->len--;
        return 0;
    }
    else{
        link_node_t* temp=p->head;//用temp指代要删除的节点，
        for(int i =0;i<post;i++){
            temp=temp->next;
        }
        temp->prior->next=temp->next;
        temp->next->prior=temp->prior;
        free(temp); 
        p->len--;
        return 0;
    }
    if(p->head->next == NULL){
        p->tail = p->head;
    }
}

//5.判断双向链表是否为空
int isEmptyDoubleLinkList(const double_list_t p){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
    return p->head != p->tail;
}

//6.求双向链表的长度
int lengthDoubleLinkList(const double_list_t p){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
    return p->len;
}

//7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(const double_list_t p,datatype data){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
    link_node_t* temp=p->head->next;//用temp指代第一个节点，
    int i=0;
    while(temp != NULL){
        if(temp->data == data){
           return i;
        }
        temp=temp->next;
        i++;
    }
    return -1;
}

//8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p,int post, datatype data){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
     if(0 <= post && post < (p->len)/2){
        link_node_t* temp=p->head->next;//用temp指代第一个节点，
        for(int i =0;i<post;i++){
            temp=temp->next;
        }
        temp->data=data;
        return 0;
    }
    else if((p->len)/2 <= post && post < p->len){
        link_node_t* temp=p->tail;      //用temp指代最后一个节点，
        for(int i =(p->len)/2;i<post;i++){
            temp=temp->prior;
        }
        temp->data=data;
        return 0;
    }
    else{
        printf("修改位置不合法!\n");
        return -1;
    }
}

//9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data){
    if(p == NULL){
        printf("头尾指针内存分配错误!\n");
        return -1;
    }
    link_node_t* temp=p->head->next;//用temp指代第一个节点，
    while(temp != NULL){
        if(temp->data == data){
            if(temp == p->tail){
                temp->prior->next=NULL;
                p->tail=temp->prior;
                free(temp);
                temp=p->tail;
                p->len--;
            }
            else{
                link_node_t* ftemp=temp->next;//ftemp保留后一个节点地址
                temp->prior->next=temp->next;
                temp->next->prior=temp->prior;
                free(temp);
                temp=ftemp; //指针后移来进行下次寻找
                p->len--;
            }
        }
        else{
            temp=temp->next;
        }
        

    }
}